package leetcode_1301_1400;

import node.TreeNode;

public class LeeCode_1373 {
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n10 = new TreeNode(10);
        TreeNode n_5 = new TreeNode(-5);
        TreeNode n20 = new TreeNode(20);
        n1.right = n10;
        n10.left = n_5;
        n10.right = n20;
        System.out.println(maxSumBST(n1));
    }

    private static int maxSumBST(TreeNode root) {
        int[] ans = new int[1];
        ans[0] = Integer.MIN_VALUE;
        dfs(root, ans);
        return Math.max(0, ans[0]);
    }
    private static int[] dfs(TreeNode node, int[] ans){
        if (node == null)
            return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        int[] left = dfs(node.left, ans);
        int[] right = dfs(node.right, ans);
        int x = node.val;
        if (x > left[1] && x < right[0]){
            int s = right[2] + left[2] + x;
            ans[0] = Math.max(ans[0], s);
            return new int[]{Math.min(left[0], x), Math.max(right[1], x), s};
        }else {
            return new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
        }
    }
}
